import java.util.ArrayList;
import java.util.List;

public class Test {
    /**
     * 水果成篮
     * @param fruits
     * @return
     */
    public int totalFruit(int[] fruits) {
        int n = fruits.length;
        int[] hash = new int[n];
        int ret = 0;
        for (int left = 0, right = 0, kinds = 0; right < n; right++) {
            if (hash[fruits[right]] == 0) {
                kinds++;
            }
            hash[fruits[right]]++;
            while (kinds > 2) {
                hash[fruits[left]]--;
                if (hash[fruits[left]] == 0) {
                    kinds--;
                }
                left++;
            }
            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }

    /**
     * 找到字符串中所有字母异位词
     * @param ss
     * @param pp
     * @return
     */
    public List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> ret = new ArrayList<>();
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        int[] hash1 = new int[26];  // 统计字符串 p1 中每个字符字符出现的个数
        for (char ch : p) {
            hash1[ch - 'a']++;
        }

        int[] hash2 = new int[26];  // 统计窗口中每一个字符出现的个数
        for (int left = 0,right = 0,count = 0; right < s.length; right++) {
            char in = s[right];
            // 进窗口
            hash2[in - 'a']++;
            if (hash2[in - 'a'] <= hash1[in - 'a']) {   // 维护count
                count++;
            }

            // 判断
            if (right - left + 1 > p.length) {
                char out = s[left];
                left++;
                if (hash2[out - 'a'] <= hash1[out - 'a']) {    // 维护count
                    count--;
                }
                // 出窗口
                hash2[out - 'a']--;
            }

            // 更新结果
            if (count == p.length) {
                ret.add(left);
            }
        }
        return  ret;
    }

}
